#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>


struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;

        if (list1->val > list2->val)
        {
            list2->next = mergeTwoLists(list2->next, list1);
            return list2;
        }
        else
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
    }
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        return dfs(list1, list2);
    }

    ListNode* dfs(ListNode* l1, ListNode* l2)
    {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;

        if (l1->val > l2->val)
        {
            l2->next = dfs(l2->next, l1);
            return l2;
        }
        else
        {
            l1->next = dfs(l1->next, l2);
            return l1;
        }
    }
};